In multiple processor or "multiprocessor" (MP) computers, it is sometimes necessary to ensure that one of the processors has exclusive access to a data structure or system resource for a period of time. This is typically achieved by using a software locking or latching technique such as a semaphore.
A test-and-set primitive may be implemented in hardware that supports the software latching technique. A test-and-set primitive permits software to read a variable (of a data structure), compare it in some way and write back a result based on the comparison, in an indivisible and uninterrupted fashion with respect to other system processors.
Since semaphore and like latched variables are inherently shared, access to them in a MP system can consume a lot of memory band width and processor time in looping on unavailable variables.
These variables also tend to spend a significant amount of time being moved from the cache of one processor to the cache of another. This is particularly true when the test-and-set hardware primitive is used to test the status of the semaphore, since the primitive involves a write operation which will cause cache ownership and therefore data exchange between the testing processor and the processor with the more current cached copy of the data. A software technique of minimizing band width utilization is the "spin lock" and an example of this technique is as follows. If a hardware test-and-set primitive is utilized for an initial test and the variable under test is currently owned by another processor, then the software loops on reading the variable until it becomes free, hence "spinning." This spinning occurs inside the cache and thus reduces impact on system resources such as memory bandwidth. After the variable becomes free, the test-and-set operation is used in an attempt to gain ownership of the variable, hence "locking."
The spin lock technique, however, has dis-advantageous aspects. One disadvantageous aspect is that in a multiprocessor system, several of the processors may desire the same variable and simultaneously institute a spin lock for ownership. When the processor that is currently accessing the variable finishes, each processor that is spinning on the variable tries to lock onto it, creating a "thundering herd" scenario. A thundering herd situation is particularly disadvantageous when one processor has an advantage in gaining access to a variable over another processor, for example, due to system architecture, such as location on a bus, or other reasons.
With respect to uneven placement on a bus, in this situation one processor may be more likely to lock onto a variable than another, resulting in uneven access and the degradation or suspension of operations in the disadvantaged processor. This positional favoritism might arise in a MP computing system such as that shown in FIG. 1 which utilizes a bus hierarchy with a multiplicity of local busses interconnected by a system bus. A processor in the left-hand cluster of processors has an advantage over processors in the right-hand cluster of processors when attempting to access a semaphore in the left-hand cluster. It should also be recognized that system architecture such as that of FIG. 1 (tiered busses) are gaining popularity over system architectures that use a single shared bus, due to the physical and electrical limitations associated with putting, many processors on a single shared bus. The move in the art towards system architecture such as those discussed below further increases the significance of the present invention.